package e_ch13_directedG.CircleDetection_SP;

import e_ch13_directedG.graph_final.Graph_final_try;

/*
 * 在无向图中，遍历出现沿来路返回的话并不算环，所以二次访问到某顶点时，需要确认是从新的方向二次访问到了； 
 *	但在有向图里，两点之间的你来我往也属于环，
 *			而且！！！  有新路径二次访问顶点 不一定就是环，具体如图：有向图环检测的不同.png，之所以在无向图行得通是由于无向边的特殊性；
 *
 *原理（原理图解.png）：
 *其实本质上，检测环形路径应该是那种感觉：我在走迷宫，走过的轨迹斗折蛇行的向前，前面有岔口，我选了一条路走到底是死胡同，于是我原路返回 尝试另一个分岔口，这个时候如果再访问到另一个分叉口，也只是有多条路径而已，
 * 		真正属于回路的，是我走着走着又回到了我前边走过来的路上，走过的路径才能保证是通的，而不止是二次访问到而已，如果想上边这样二次访问到平行位置的路，是不能说明从平行位置可以反方向回到分岔口的；
 *
 *我退回来的路就不算了，就不在我当前走过的路径上了(从起点到现在的位置)，必须是回到了当前路径里走过的地方才一定是出现了环，“环的要求”是比“多条路径的要求”更高的，后者还需要满足onPath的条件才等于前者，即三角形的第三条边要保证走得通；
 */
public class DirectedCycleDetection {   
	
    private Graph_final_try G;
    private boolean[] visited;
    private boolean[] onPath;
    private boolean hasCycle = false;

    public DirectedCycleDetection(Graph_final_try G){

        if(!G.isDirected())
            throw new IllegalArgumentException("DirectedCycleDetection only works in directed graph.");

        this.G = G;
        visited = new boolean[G.V()];
        onPath = new boolean[G.V()];
        for(int v = 0; v < G.V(); v ++)
            if(!visited[v])
                if(dfs(v)){
                    hasCycle = true;
                    break;
                }
    }

    // 从顶点 v 开始，判断图中是否有环
    private boolean dfs(int v){   //而上边场景的描述就是dfs的过程；

        visited[v] = true;
        onPath[v] = true;
        for(int w: G.adj(v))
            if(!visited[w]){  //没访问过的就去访问；
                if(dfs(w)) return true;
            }
            else if(onPath[w]) //出现环的基础是出现二次访问，但对于有向图 并不需要排除沿来路返回一步的情况；
                return true;
        onPath[v] = false; //执行到这里 说明递归终止了，fore说明是分路递归，但不管哪一路，终止条件都是走到死路了，即fore进不去了； 这时候向递归上层回退，就应该去掉绿色(即onPath置false)
        return false;
    }

    public boolean hasCycle(){
        return hasCycle;
    }

    public static void main(String[] args){

        Graph_final_try g = new Graph_final_try("ug.txt", true);
        DirectedCycleDetection cycleDetection = new DirectedCycleDetection(g);
        System.out.println(cycleDetection.hasCycle());

        Graph_final_try g2 = new Graph_final_try("ug2.txt"); // error
        DirectedCycleDetection cycleDetection2 = new DirectedCycleDetection(g2);
        System.out.println(cycleDetection2.hasCycle());
    }
}